import collections
max_range = 10 ** 5 + 1
q = [1] * max_range
st = []
for i in range(2, max_range):
    if q[i] == 1:
        st.append(i)
        q[i] = i
    for num in st:
        if num * i < max_range:
            q[num * i] = num
        else:
            break
        if i % num == 0:
            break

class Solution(object):
    def gcdSort(self, nums):
        n = len(nums)
        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]
        
        def union(x, y):
            rx = find(x)
            ry = find(y)
            if rx != ry:
                if rx > ry:
                    p[rx] = ry
                else:
                    p[ry] = rx

        p = {num: num for num in st}
        for num in nums:
            a = set()
            while num > 1:
                a.add(q[num])
                num = num // q[num]
            a = list(a)
            m = len(a)
            for i in range(1, m):
                union(a[i - 1], a[i])
        root = [-1] * n
        sd = collections.defaultdict(list)
        for index, num in enumerate(nums):
            if q[num] != 1:
                root[index] = find(q[num])
                sd[root[index]].append(num)
        sd_index = collections.defaultdict(int)
        for key in sd:
            sd[key].sort()
        new_num = []
        for index, num in enumerate(nums):
            g = root[index]
            if g == -1:
                new_num.append(num)
            else:
                val = sd[g][sd_index[g]]
                new_num.append(val)
                sd_index[g] += 1
            if index > 0:
                if new_num[-1] < new_num[-2]:
                    return False
        return True








data = Solution()
nums = [5,2,6,2]
print(data.gcdSort(nums))